In the computer industry, memory devices, such as hard and floppy disk drives and Random Access Memory (RAM), provide a common means for storing computer information. Typically, space is allocated in and data is stored to and retrieved from these storage mediums through hardware and software adapted for that purpose. For example, a computer operating system will often provide the necessary interface with a user or process ("Process") for accessing the storage medium to retrieve data, delete data, or to allocate free space for storing new data therein.
Often, when data is written to a disk drive, it is written and stored in an inefficient manner. For example, when data is to be saved to the disk, the interfacing Process will seek out a storage space location on the disk that is available and free to be used (i.e., not already occupied with existing data or reserved for some purpose), and the data is written to that identified available location. However, if more contiguous storage space is required than is available on the disk in one contiguous location, an insufficient disk space error may occur. Consequently, the Process attempting to consume disk space (write the data to disk) is unable to satisfy its request and must wait until more contiguous disk space becomes available. An insufficient amount of contiguous space may be the result of the disk space having become fragmented. As a storage medium continues to be used, it can easily become quite fragmented so that no large contiguous block of storage space is available. In this context, fragmentation constitutes inefficiently used disk space when a sufficient amount of contiguous disk space is unavailable to satisfy a consumption request.
Another example of inefficient use of storage space in a storage medium is data stored in a non-compressed format. Data stored on disk in a compressed format consumes less disk space and represents a more efficient use of disk space. Since disk capacity is always a limited amount, data compression is a desirable feature.
Yet another instance of inefficient use of storage space is seen in the comparison of the amount of redundant data stored in various data protection schemes. For example, where a plurality of storage mediums are used, such as in a Redundant Array of Independent Disks (RAID or disk array), the use of disk mirroring (RAID Level 1) and parity checking (RAID Level 5) data redundancy protection schemes are commonly employed. Although RAID 1 provides the highest data reliability and typically provides the best Input/Output (I/O) performance, it uses the most amount of storage space because all data is duplicated. In contrast, although RAID 5 provides a lesser amount of data reliability and, typically, reduced I/O performance, it doesn't consume as much disk space as a RAID 1 technique because data is not duplicated but rather parity checked across the disk array. Accordingly, literal disk storage space is, effectively, used more efficiently in a RAID 5 technique compared to a RAID 1 method.
Several problems arise with data being stored inefficiently on disk drives and other storage mediums. First, some requests for space cannot be satisfied with fragmented free space. Second, non-compressed data takes up more disk space than compressed data, and certain data redundancy techniques take up more disk space than others, thus limiting the total amount of data capable of being stored on the disk. Third, separate processing must occur to convert inefficiently stored data to more efficiently stored data in order to create more usable free disk space from the limited amount of existing space. Fourth, when substantially concurrent Processes request the consumption of disk space and data is stored inefficiently on the disk or free space is being generated concurrently on the disk, there exists the potential for an unfair consumption of disk space by one of the Processes over the other.
As an example, assume that a first Process requests to consume disk space but is unable to allocate its required amount because insufficient disk space exists to satisfy its request. The insufficient disk space may be the result of any number of the inefficiencies in disk space usage discussed. Assume also that a second Process contends for consumption of disk space substantially concurrently with but immediately after the first Process has made its request. Assume also, then, that space is made available by some means after the first Process makes its request but substantially concurrently with the second Process making its request. This space may be made available by any means discussed, such as deletion of data from the disk, compression of data on the disk, or any other conceivable means for freeing up disk space. At the instant that the space is made available, it is possible that the second Process will consume the disk space before the first Process because the second Process requested the space at substantially the same time the space became available. Consequently, the second Process allocates and consumes the free space before the first Process is able to allocate its requested amount, even though the first Process was first in time to request space. In essence, a contention for space occurs, and the second Process unfairly consumes the space relative to the first Process.
This example demonstrates the problem of unfair allocation of disk space by a Process when multiple Processes contend for disk space, insufficient disk space exists to satisfy the disk space consumption requests, and the generation of free space from inefficiently used space is an event that needs to occur to provide more usable disk space.
Although efforts have been made to address these problems, a completely satisfactory solution has not been presented. For example, certain software utilities have been developed to defragment a hard disk drive. However, generally these utilities do not work concurrently with Processes requesting disk space usage but must be executed at discrete moments when no other disk activity is occurring. Other utilities compress data on a disk drive, and some even work concurrently with Process activity in consuming disk space, but none work in conjunction with the other disk space inefficiency problems. Furthermore, although various RAID techniques are available for data redundancy use, the facility to alternate between the techniques upon a concurrent demand for disk space has not been offered in conjunction with the other disk space inefficiency problems. In essence, nothing in the art provides a comprehensive solution to manage each of the aforementioned disk space inefficiencies concurrently during Process contention for disk space and, yet, also ensures a fair disk space consumption by the requesting Processes.
Accordingly, objects of the present invention are to provide a memory management system wherein responsive to a recognized need for more storage space and responsive to Process requests for storage space consumption in a limited storage space environment, inefficiently used storage space is converted to efficiently used storage space and free space, and competing Processes are allowed to allocate free storage space only pursuant to an ordering control scheme conveying elements of fairness for allocation of the free space.